LeetCode 139. Word Break 单词拆分

Posted on | In

139. Word Break 单词拆分

题目描述

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

示例:

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

解答1

第一种思路是用DFS的思路来做，先遍历string，当遇到一个wordDict中存在的单词的时候，我们记住当前位置，然后将string的剩余部分进入循环。如果剩余部分都在wordDict里面，那么DFS就返回true。如果尝试所有位置都不成功的话，DFS就返回false。

注意在这个过程中要维护一个set，里面记录string的哪个位置（即index）不能成功，那次再碰到这个位置的时候就直接返回false。如果不维护这个set会超时。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
set<int> mem;

public:
    bool wordBreak(string s, vector<string>& wordDict) {
        return DFS(s, 0, wordDict);

    }
private: 
	bool DFS(string s, int index, vector<string>& wordDict) {
		if (index == s.size())
			return true;
		if (mem.find(index) != mem.end())
			return false;
        for (int i = index + 1; i < s.size(); i++) {
        	string str = s.substr(index, i - index);
        	if (find(wordDict.begin(), wordDict.end(), str) != wordDict.end()) {
        			
        			if (DFS(s, i, wordDict)) {
        				return true;
        			}
        			else
        				mem.insert(i);

        		
        	}
        }
        mem.insert(index);
        return false;
	}
};

解答2

第二种思路是用DP，DP的每一个index中存的是一个bool类型的值，表明以该index之前的word是否可以从wordDict当中组成。

我们设置两个变量i和j，i用来遍历string，j的取值范围是0到i - 1。

在遍历的过程中判断j到i之间的字符串是否合法，如果合法并且dp[j]为true的情况下，就说明dp[i]为true。

最后返回dp[s.size()] 的结果。

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(s.size() == 0) return false;
        vector<int> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i ++) {
            for (int j = i - 1; j >= 0; j --) {
                if (dp[j]) {
                    string str = s.substr(j, i - j);
                    if (find(wordDict.begin(), wordDict.end(), str) != wordDict.end()) {
                        dp[i] = true;
                        break;
                    }
                }
            dp[i] = false;
            }
        }
    return dp[s.size()];
    }
};